package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

import java.util.LinkedList;

/**
 * 草他娘居然做错了
 * 难道我只配拿 13k
 */
public class _98_is_valid_bst {
    
    public boolean isValidBST1(TreeNode root) {
        return dfs(root);
    }
    
    Integer prev;
    
    boolean dfs(TreeNode node) {
        if (node == null) return true;
        boolean valid = dfs(node.left);
        if (!valid) return false;
        if (prev != null && node.val <= prev) return false;
        prev = node.val;
        return dfs(node.right);
    }
    
    /**
     * 我真没想到做这个题还有悬念
     * <p>
     * 哎我草不干人事
     * 玩阴的是吧，又？
     */
    public boolean isValidBST(TreeNode root) {
        return recur(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    boolean recur(TreeNode node, long lower, long upper) {
        if (node == null) return true;
        if (node.val <= lower || node.val >= upper) return false;
        return recur(node.left, lower, node.val) && recur(node.right, node.val, upper);
    }
    
    /**
     * 说实话中序遍历我已经玩腻了
     */
    public boolean isValidBST2(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        long prev = Long.MIN_VALUE;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            if (node.val <= prev) return false;
            prev = node.val;
            root = node.right;
        }
        return true;
    }
}
